package busquedasheuristicas.primeromejor;


import java.util.ArrayList;
import java.util.Arrays;
import java.util.TreeMap;

import busquedasciegas.EstadoPuzzle.Key;


/**
 * Implementacion del algoritmo de busqueda
 * heuristica primero el mejor
 * @author german
 *
 */
public class PrimeroMejor{

	ArrayList<EstadoHeuristica> cola;
	TreeMap<Key, EstadoHeuristica> arbol;
	
	public PrimeroMejor(){
		cola = new ArrayList<EstadoHeuristica>();
		arbol = new TreeMap<Key, EstadoHeuristica>();
	}
	
	private String buscar(EstadoHeuristica inicial, int[] meta){
		
		EstadoHeuristica actual = null; 
		EstadoHeuristica estadoMeta = new EstadoHeuristica(meta, null);
		String traza = "";
		ArrayList<EstadoHeuristica> hijos = new ArrayList<EstadoHeuristica>();
		
		inicial.setVisitado(true);
		arbol.put(inicial.key, inicial);
		
		actual = inicial;
		hijos = actual.generarDescendientes(meta);
		
		for (EstadoHeuristica hijo : hijos) {
			cola.add(hijo);
			arbol.put(hijo.key, hijo);
		}
		
		EstadoHeuristica[] hijosArreglo; 
		
		while (!arbol.containsKey(estadoMeta.key)){

			hijosArreglo = new EstadoHeuristica[cola.size()];
			cola.toArray(hijosArreglo);
			
			// extraer estado con menor mejor heuristica
			Arrays.sort(hijosArreglo);
			actual = hijosArreglo[0];
			hijos = actual.generarDescendientes(meta);
			cola.remove(cola.indexOf(actual));
			
			for (EstadoHeuristica hijo : hijos) {
				if (!cola.contains(hijo) && (!hijo.isVisitado())){
					cola.add(hijo);
					arbol.put(hijo.key, hijo);
					hijo.setVisitado(true);
				}
			}
		
			cola.toArray(hijosArreglo);
			System.out.println(cola.size());
			
		}
		traza = hallarTraza(inicial, arbol.get(estadoMeta.key));
		return traza;
		
	}
	
	/**
	 * Busca en la estructura árbol construida en la función Buscar
	 * el camino o traza que lleva del estado inicial al estado final.
	 * @param raiz Representación del estado inicial.
	 * @param meta Representación del estado final, meta u
	 * objetivo.
	 */
	public String hallarTraza(EstadoHeuristica raiz, EstadoHeuristica meta){
		
		String oper = "";
		EstadoHeuristica actual = arbol.get(meta.key);
		
		ArrayList<EstadoHeuristica> sol = new ArrayList<EstadoHeuristica>();
		while (actual != null){
			sol.add(actual);
			actual = actual.padre;
		}
		oper = oper + "Solucion: " + "\n";
		int numMov = sol.size();
		for(int i = 0; i < numMov; i++){
			oper = oper + sol.get(sol.size()-1) + "\n";
			sol.remove(sol.size()-1);
		}
		return oper;
	}
	
	public static void main(String[] args) {
		ArrayList<Integer> inicial = new ArrayList<Integer>();
		ArrayList<Integer> inicial2 = new ArrayList<Integer>();
		
		int[] meta = new int[9];
		meta[0] = 1;
		meta[1] = 2;
		meta[2] = 3;
		meta[3] = 8;
		meta[4] = 0;
		meta[5] = 4;
		meta[6] = 7;
		meta[7] = 6;
		meta[8] = 5;

		// estado inicial
		inicial.add(2);
		inicial.add(8);
		inicial.add(3);
		inicial.add(1);
		inicial.add(6);
		inicial.add(4);
		inicial.add(7);
		inicial.add(0);
		inicial.add(5);
		
		inicial2.add(2);
		inicial2.add(8);
		inicial2.add(4);
		inicial2.add(1);
		inicial2.add(6);
		inicial2.add(3);
		inicial2.add(7);
		inicial2.add(0);
		inicial2.add(5);
		
		PrimeroMejor pm = new PrimeroMejor();
		EstadoHeuristica e = new EstadoHeuristica(inicial2, meta);
		System.out.println(pm.buscar(e, meta));
		
		/* Prueba 1
		EstadoHeuristica e = new EstadoHeuristica(inicial, meta);
		EstadoHeuristica e2 = new EstadoHeuristica(inicial2, meta);
		EstadoHeuristica[] estados = new EstadoHeuristica[2];
		estados[0] = e2;
		estados[1] = e;
		Arrays.sort(estados);
		
		for (EstadoHeuristica estado : estados) {
			System.out.println(estado + ": " + estado.h);
		}
		*/
	}
	
	
	
}
